package com.zhugang.week13.binarysearch;

/**
 * @program algorithms
 * @description: MySqrt
 * @author: chanzhugang
 * @create: 2022/11/25 20:58
 */
public class MySqrt {

    /**
     * 69 X 的平方根
     * https://leetcode.cn/problems/sqrtx/
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        /**
         * 不好想，转成二分问题
         * 找最后一个平方 <= x 的数
         * 0 - x 之间找 k， 使k^2 <= x
         */
        if (x == 0) {
            // leetcode 特殊处理
            return 0;
        }
        int low = 1;
        int high = x / 2 + 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long mid2 = (long) mid * mid;
            if (mid2 == x) {
                return mid;
            } else if (mid2 < x) {
                // 向后探测
                long mid22 = (long) (mid + 1) * (mid + 1);
                if (mid22 <= x) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}